{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #排序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers #divide-and-conquer #sorting #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针 #分治 #排序 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #排序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定链表的头结点&nbsp;<code>head</code>&nbsp;，请将其按 <strong>升序</strong> 排列并返回 <strong>排序后的链表</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg\" style=\"width: 302px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>head = [4,2,1,3]\n",
    "<b>输出：</b>[1,2,3,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg\" style=\"width: 402px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>head = [-1,5,3,4,0]\n",
    "<b>输出：</b>[-1,0,3,4,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>head = []\n",
    "<b>输出：</b>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目在范围&nbsp;<code>[0, 5 * 10<sup>4</sup>]</code>&nbsp;内</li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>进阶：</b>你可以在&nbsp;<code>O(n&nbsp;log&nbsp;n)</code> 时间复杂度和常数级空间复杂度下，对链表进行排序吗？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 148&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/sort-list/\">https://leetcode-cn.com/problems/sort-list/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [7WHec2](https://leetcode.cn/problems/7WHec2/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [7WHec2](https://leetcode.cn/problems/7WHec2/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,1,3]', '[-1,5,3,4,0]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def merge(head1: ListNode, head2: ListNode) -> ListNode:\n",
    "            dummyHead = ListNode(0)\n",
    "            temp, temp1, temp2 = dummyHead, head1, head2\n",
    "            while temp1 and temp2:\n",
    "                if temp1.val <= temp2.val:\n",
    "                    temp.next = temp1\n",
    "                    temp1 = temp1.next\n",
    "                else:\n",
    "                    temp.next = temp2\n",
    "                    temp2 = temp2.next\n",
    "                temp = temp.next\n",
    "            if temp1:\n",
    "                temp.next = temp1\n",
    "            elif temp2:\n",
    "                temp.next = temp2\n",
    "            return dummyHead.next\n",
    "        \n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        length = 0\n",
    "        node = head\n",
    "        while node:\n",
    "            length += 1\n",
    "            node = node.next\n",
    "        \n",
    "        dummyHead = ListNode(0, head)\n",
    "        subLength = 1\n",
    "        while subLength < length:\n",
    "            prev, curr = dummyHead, dummyHead.next\n",
    "            while curr:\n",
    "                head1 = curr\n",
    "                for i in range(1, subLength):\n",
    "                    if curr.next:\n",
    "                        curr = curr.next\n",
    "                    else:\n",
    "                        break\n",
    "                head2 = curr.next\n",
    "                curr.next = None\n",
    "                curr = head2\n",
    "                for i in range(1, subLength):\n",
    "                    if curr and curr.next:\n",
    "                        curr = curr.next\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "                succ = None\n",
    "                if curr:\n",
    "                    succ = curr.next\n",
    "                    curr.next = None\n",
    "                \n",
    "                merged = merge(head1, head2)\n",
    "                prev.next = merged\n",
    "                while prev.next:\n",
    "                    prev = prev.next\n",
    "                curr = succ\n",
    "            subLength <<= 1\n",
    "        \n",
    "        return dummyHead.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        def sort(head):\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "            \n",
    "            slow=head\n",
    "            fast=head.next\n",
    "            while fast and fast.next:\n",
    "                slow=slow.next\n",
    "                fast=fast.next.next\n",
    "\n",
    "            h1=slow.next\n",
    "            slow.next=None\n",
    "            return merge(sort(head),sort(h1))\n",
    "        \n",
    "        def merge(l1,l2):\n",
    "            cur=node=ListNode(0)\n",
    "            while l1 and l2:\n",
    "                if l1.val<l2.val:\n",
    "                    node.next=l1\n",
    "                    l1=l1.next\n",
    "                else:\n",
    "                    node.next=l2\n",
    "                    l2=l2.next\n",
    "                node=node.next\n",
    "            if l1:\n",
    "                node.next=l1\n",
    "            else:\n",
    "                node.next=l2\n",
    "            \n",
    "            return cur.next\n",
    "        \n",
    "        \n",
    "        return sort(head)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def sort(head, tail):\n",
    "            if not head:\n",
    "                return head\n",
    "            if head.next == tail:\n",
    "                head.next = None\n",
    "                return head\n",
    "\n",
    "            slow = head\n",
    "            fast = head\n",
    "            while slow != tail and fast != tail and fast.next != tail:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            \n",
    "            return merge(sort(head, slow), sort(slow, tail))\n",
    "        \n",
    "        def merge(head1, head2):\n",
    "            tmp = ListNode(0)\n",
    "            cur = tmp\n",
    "            cur1 = head1\n",
    "            cur2 = head2\n",
    "            \n",
    "            while cur1 and cur2:\n",
    "                if cur1.val < cur2.val:\n",
    "                    cur.next = cur1\n",
    "                    cur1 = cur1.next\n",
    "                else:\n",
    "                    cur.next = cur2\n",
    "                    cur2 = cur2.next\n",
    "                cur = cur.next\n",
    "            \n",
    "            if cur1:\n",
    "                cur.next = cur1\n",
    "            if cur2:\n",
    "                cur.next = cur2\n",
    "            \n",
    "            return tmp.next\n",
    "        \n",
    "        return sort(head, None)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:\n",
    "            if not head: return head\n",
    "            if head.next == tail:\n",
    "                head.next = None\n",
    "                return head\n",
    "            slow = fast = head\n",
    "            while fast != tail:\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "                if fast != tail:\n",
    "                    fast = fast.next\n",
    "            mid = slow\n",
    "            return merge(sortFunc(head, mid), sortFunc(mid, tail))\n",
    "        def merge(head1: ListNode, head2: ListNode) -> ListNode:\n",
    "            dummyHead = ListNode(0)\n",
    "            temp, temp1, temp2 = dummyHead, head1, head2\n",
    "            while temp1 and temp2:\n",
    "                if temp1.val <= temp2.val:\n",
    "                    temp.next = temp1\n",
    "                    temp1 = temp1.next\n",
    "                else:\n",
    "                    temp.next = temp2\n",
    "                    temp2 = temp2.next\n",
    "                temp = temp.next\n",
    "            if temp1:\n",
    "                temp.next = temp1\n",
    "            elif temp2:\n",
    "                temp.next = temp2\n",
    "            return dummyHead.next\n",
    "        return sortFunc(head, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:\n",
    "            if head == None: return head\n",
    "            if head.next == tail: \n",
    "                head.next = None\n",
    "                return head\n",
    "            slow, fast = head, head\n",
    "            while fast != tail:\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "                if fast != tail:\n",
    "                    fast = fast.next\n",
    "            mid = slow\n",
    "            return merge(sortFunc(head, mid), sortFunc(mid, tail))\n",
    "        def merge(head1: ListNode, head2: ListNode) -> ListNode:\n",
    "            ans = ListNode(0, None)\n",
    "            temp, temp1, temp2 = ans, head1, head2\n",
    "            while temp1 and temp2:\n",
    "                if temp1.val <= temp2.val:\n",
    "                    temp.next = temp1\n",
    "                    temp1 = temp1.next\n",
    "                else:\n",
    "                    temp.next = temp2\n",
    "                    temp2 = temp2.next\n",
    "                temp = temp.next\n",
    "            if temp1:\n",
    "                temp.next = temp1\n",
    "            elif temp2:\n",
    "                temp.next = temp2\n",
    "            return ans.next\n",
    "        return sortFunc(head, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:\n",
    "            if not head: return head\n",
    "            if head.next == tail:\n",
    "                head.next = None\n",
    "                return head\n",
    "            slow, fast = head, head\n",
    "            while fast != tail:\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "                if fast != tail:\n",
    "                    fast = fast.next\n",
    "            mid = slow\n",
    "            return merge(sortFunc(head, mid), sortFunc(mid, tail))\n",
    "            # if not head: return head\n",
    "            # if head.next == tail:\n",
    "            #     head.next = None\n",
    "            #     return head\n",
    "            # slow = fast = head\n",
    "            # while fast != tail:\n",
    "            #     slow = slow.next\n",
    "            #     fast = fast.next\n",
    "            #     if fast != tail:\n",
    "            #         fast = fast.next\n",
    "            # mid = slow\n",
    "            # return merge(sortFunc(head, mid), sortFunc(mid, tail))\n",
    "        def merge(head1: ListNode, head2: ListNode) -> ListNode:\n",
    "            ans = ListNode(0)\n",
    "            temp, temp1, temp2 = ans, head1, head2\n",
    "            while temp1 and temp2:\n",
    "                if temp1.val <= temp2.val:\n",
    "                    temp.next = temp1\n",
    "                    temp1 = temp1.next\n",
    "                else:\n",
    "                    temp.next = temp2\n",
    "                    temp2 = temp2.next\n",
    "                temp = temp.next\n",
    "            if temp1: temp.next = temp1\n",
    "            elif temp2: temp.next = temp2\n",
    "            return ans.next\n",
    "            # dummyHead = ListNode(0)\n",
    "            # temp, temp1, temp2 = dummyHead, head1, head2\n",
    "            # while temp1 and temp2:\n",
    "            #     if temp1.val <= temp2.val:\n",
    "            #         temp.next = temp1\n",
    "            #         temp1 = temp1.next\n",
    "            #     else:\n",
    "            #         temp.next = temp2\n",
    "            #         temp2 = temp2.next\n",
    "            #     temp = temp.next\n",
    "            # if temp1:\n",
    "            #     temp.next = temp1\n",
    "            # elif temp2:\n",
    "            #     temp.next = temp2\n",
    "            # return dummyHead.next\n",
    "        return sortFunc(head, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        def sort_merge(l1: ListNode, l2: ListNode):\n",
    "            dummy = ListNode(0)\n",
    "            curr = dummy\n",
    "            while l1 and l2:\n",
    "                if l1.val < l2.val:\n",
    "                    curr.next, l1 = l1, l1.next\n",
    "                else:\n",
    "                    curr.next, l2 = l2, l2.next\n",
    "                curr = curr.next\n",
    "            curr.next = l1 if l1 else l2\n",
    "            return dummy.next\n",
    "\n",
    "        def partition(node: ListNode):\n",
    "            if not node or not node.next:\n",
    "                return node\n",
    "            slow, fast = node, node.next\n",
    "            while fast and fast.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            mid, slow.next = slow.next, None\n",
    "            left = partition(node)\n",
    "            right = partition(mid)\n",
    "\n",
    "            return sort_merge(left, right)\n",
    "\n",
    "        return partition(head)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if (not head) or (not head.next):\n",
    "            return head\n",
    "        length = 0\n",
    "        current = head\n",
    "        \n",
    "        while current:\n",
    "            length+=1\n",
    "            current = current.next\n",
    "        print('length:',length)\n",
    "        mid =floor(length/2)\n",
    "        # print(mid)\n",
    "        current = head\n",
    "        for i in range(mid-1):\n",
    "            \n",
    "            current = current.next\n",
    "            print(current.val)\n",
    "            \n",
    "        \n",
    "        head2 = current.next\n",
    "        current.next = None\n",
    "\n",
    "        head1 = self.sortList(head)\n",
    "        head2 = self.sortList(head2)\n",
    "\n",
    "        return self.merge(head1,head2)\n",
    "    def merge(self,head1,head2):\n",
    "        head = None\n",
    "        if not head:\n",
    "            if head1.val <=head2.val:\n",
    "                head = head1\n",
    "                head1 = head1.next\n",
    "            else:\n",
    "                head = head2\n",
    "                head2 = head2.next\n",
    "        current = head\n",
    "        while head1 and head2:\n",
    "            if head1.val <=head2.val:\n",
    "                current.next = head1\n",
    "                head1 = head1.next\n",
    "            else:\n",
    "                current.next = head2\n",
    "                head2 = head2.next\n",
    "            current = current.next\n",
    "        \n",
    "        if head1:\n",
    "            current.next = head1\n",
    "        else:\n",
    "            current.next = head2\n",
    "\n",
    "        return head\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        ls = []\n",
    "        while head:\n",
    "            ls.append(head)\n",
    "            head = head.next\n",
    "        ls.sort(key = lambda x:x.val)\n",
    "        start = cur = ListNode()\n",
    "        for node in ls:\n",
    "            node.next = None\n",
    "            cur.next = node\n",
    "            cur = cur.next\n",
    "        return start.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        # group = []\n",
    "        # head_2 = head\n",
    "        # while head_2:\n",
    "        #     group.append(head_2.val)\n",
    "        #     head_2 = head_2.next\n",
    "        # group.sort()\n",
    "        # new_head = tail = ListNode(-1)\n",
    "        # for item in group:\n",
    "        #     tail.next = ListNode(item)\n",
    "        #     tail = tail.next\n",
    "        # return new_head.next\n",
    "\n",
    "        # if head is None:\n",
    "        #     return head\n",
    "        # new_head = ListNode(0)\n",
    "        # new_head.next = head\n",
    "        # sorted_head = new_head\n",
    "        # while sorted_head.next:\n",
    "        #     current = sorted_head.next\n",
    "        #     if not current.next:\n",
    "        #         break\n",
    "        #     if current.next.val < current.val:\n",
    "        #         temp = current.next\n",
    "        #         current.next = temp.next\n",
    "        #         temp.next = sorted_head.next\n",
    "        #         sorted_head.next = temp\n",
    "        #         sorted_head = new_head\n",
    "        #     else:\n",
    "        #         sorted_head = sorted_head.next\n",
    "        # sorted_head = new_head.next\n",
    "        # sorted_head = new_head\n",
    "        # sorted_list = sorted_head\n",
    "        # sorted_head = sorted_head.next\n",
    "        # return sorted_head\n",
    "\n",
    "\n",
    "        # def change(pos):\n",
    "        #     new_head = pos\n",
    "        #     if pos is None:\n",
    "        #         return head\n",
    "        #     else:\n",
    "        #         current_code = ListNode(1000000)\n",
    "        #         current_code.next = pos\n",
    "        #         while new_head.next and new_head.val < new_head.next.val:\n",
    "        #             new_head = new_head.next\n",
    "        #             current_code = current_code.next\n",
    "        #         if new_head.next is None:\n",
    "        #             return pos\n",
    "        #         if current_code.val == 1000000:\n",
    "        #             next_code = new_head.next\n",
    "        #             current_code.next = next_code\n",
    "        #             new_head.next = next_code.next\n",
    "        #             next_code.next = new_head\n",
    "        #             pos = next_code\n",
    "        #         else:\n",
    "        #             next_code = new_head.next\n",
    "        #             current_code.next = next_code\n",
    "        #             new_head.next = next_code.next\n",
    "        #             next_code.next = new_head\n",
    "        #         return change(pos)\n",
    "\n",
    "        # new_head = head\n",
    "        # return change(head)\n",
    "\n",
    "\n",
    "        # from collections import deque\n",
    "\n",
    "\n",
    "        # def merge(head_1, head_2):\n",
    "        #     dummy_head = cur_node = ListNode(-1)\n",
    "        #     while head_1 and head_2:\n",
    "        #         if head_1.val < head_2.val:\n",
    "        #             cur_node.next = head_1\n",
    "        #             head_1 = head_1.next\n",
    "        #         else:\n",
    "        #             cur_node.next = head_2\n",
    "        #             head_2 = head_2.next\n",
    "        #         cur_node = cur_node.next\n",
    "        #     if head_1 is None:\n",
    "        #         cur_node.next = head_2\n",
    "        #     else:\n",
    "        #         cur_node.next = head_1\n",
    "        #     return dummy_head.next\n",
    "\n",
    "\n",
    "        # new_head = head\n",
    "        # group = deque()\n",
    "        # while new_head:\n",
    "        #     next_code = new_head.next\n",
    "        #     new_head.next = None\n",
    "        #     group.append(new_head)\n",
    "        #     new_head = next_code\n",
    "        # print(group)\n",
    "\n",
    "        # length = len(group)\n",
    "        # if length == 1 or length == 0:\n",
    "        #     return head\n",
    "        \n",
    "        # while len(group) > 1:\n",
    "        #     head_1 = group.popleft()\n",
    "        #     head_2 = group.popleft()            \n",
    "        #     group.append(merge(head_1,head_2))\n",
    "        # return group[0]\n",
    "\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        group = []\n",
    "        head_2 = head\n",
    "        while head_2:\n",
    "            group.append(head_2)\n",
    "            head_2 = head_2.next\n",
    "        group.sort(key=lambda x:x.val)\n",
    "        for i in range(len(group) - 1):\n",
    "            group[i].next = group[i + 1]\n",
    "        group[-1].next = None\n",
    "        return group[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head : return None\n",
    "\n",
    "        cur = head\n",
    "        res_list=[]\n",
    "        \n",
    "        while(cur):\n",
    "            res_list.append(cur)\n",
    "            cur=cur.next\n",
    "        res_list.sort(key=lambda x:x.val)\n",
    "\n",
    "        pre=res_list[0]\n",
    "        pre.next=None\n",
    "        cur=pre\n",
    "        for i in range(1,len(res_list)):\n",
    "            res_list[i].next=None\n",
    "            cur.next=res_list[i]\n",
    "            cur = res_list[i]\n",
    "\n",
    "        return pre\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        nodes = []\n",
    "        while head:\n",
    "            nodes.append(head)\n",
    "            head = head.next\n",
    "\n",
    "        nodes.sort(key=lambda el: el.val)\n",
    "        for i in range(len(nodes) - 1):\n",
    "            nodes[i].next = nodes[i + 1]\n",
    "        nodes[-1].next = None\n",
    "        return nodes[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        if(not head or head.next == None):\n",
    "            return head\n",
    "\n",
    "        array = []\n",
    "        p = head\n",
    "        while(p):\n",
    "            array.append(p)\n",
    "            p = p.next\n",
    "        \n",
    "        array = sorted(array, key = lambda item: item.val)\n",
    "\n",
    "\n",
    "        head = array[0]\n",
    "        for item in array[1:]:\n",
    "            head.next = item\n",
    "            head = head.next\n",
    "        head.next = None\n",
    "\n",
    "        return array[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        tmpNodes = list()\n",
    "        curr = head\n",
    "        while curr:\n",
    "            tmpNodes.append(curr)\n",
    "            curr = curr.next\n",
    "        \n",
    "        tmpNodes = sorted(tmpNodes, key=lambda x : x.val)\n",
    "        n = len(tmpNodes)\n",
    "        dummy = ListNode()\n",
    "        curr = dummy\n",
    "        for i in range(n):\n",
    "            curr.next = tmpNodes[i]\n",
    "            curr = curr.next\n",
    "        curr.next = None\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "        node_list = list()\n",
    "        while head != None:\n",
    "            node_list.append(head)\n",
    "            head = head.next\n",
    "        node_list = sorted(node_list, key=lambda x: x.val)\n",
    "        for i in range(len(node_list) - 1):\n",
    "            node_list[i].next = node_list[i + 1]\n",
    "        node_list[-1].next = None\n",
    "        return node_list[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        a = []\n",
    "        x = head\n",
    "        while x:\n",
    "            a.append(x.val)\n",
    "            x = x.next\n",
    "        if a == []:\n",
    "            return head\n",
    "        L = [a[0]]\n",
    "        length = 0\n",
    "        for x in a[1:]:\n",
    "            l = 0\n",
    "            r = length\n",
    "            # print(L, length+1)\n",
    "            length += 1\n",
    "            while True:\n",
    "                mid = (r-l) // 2 + l\n",
    "                # print(r, l, mid)\n",
    "                if x > L[mid]:\n",
    "                    l = mid+1\n",
    "                    if l < length:\n",
    "                        if L[l] > x:\n",
    "                            L.insert(l, x)\n",
    "                            break\n",
    "\n",
    "                    else:\n",
    "                        L.append(x)\n",
    "                        break\n",
    "                elif x == L[mid]:\n",
    "                    L.insert(mid, x)\n",
    "                    break\n",
    "                else:\n",
    "                    r = mid-1\n",
    "                    if r > -1:\n",
    "                        if L[r] < x:\n",
    "                            # print(x, r, mid, L[mid])\n",
    "                            L.insert(mid, x)\n",
    "                            break\n",
    "                    else:\n",
    "                        L.insert(0, x)\n",
    "                        break\n",
    "        print(L)\n",
    "        i = head\n",
    "        for x in L:\n",
    "            i.val = x\n",
    "            i = i.next\n",
    "        \n",
    "        return head\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        val= []\n",
    "        while head:\n",
    "            val.append((head.val, head))\n",
    "            head = head.next\n",
    "\n",
    "        val.sort(key=lambda x: x[0])\n",
    "        res = ListNode(-1)\n",
    "        tmp = res\n",
    "        for _, node in val:\n",
    "            node.next = None\n",
    "            tmp.next = node\n",
    "            tmp = tmp.next\n",
    "\n",
    "        return res.next\n",
    "\n",
    "\n",
    "    # def sortList(self, head: ListNode) -> ListNode:\n",
    "    #     if not head:\n",
    "    #         return head\n",
    "\n",
    "    #     val, node = [], []\n",
    "    #     i = 0\n",
    "    #     while head:\n",
    "    #         node.append(head)\n",
    "    #         val.append((head.val, i))\n",
    "    #         head = head.next\n",
    "    #         i += 1\n",
    "\n",
    "    #     val.sort()\n",
    "    #     res = ListNode(-1)\n",
    "    #     tmp = res\n",
    "    #     for _, i in val:\n",
    "    #         node[i].next = None\n",
    "    #         tmp.next = node[i]\n",
    "    #         tmp = tmp.next\n",
    "\n",
    "    #     return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head: return head\n",
    "\n",
    "        nodelist = []\n",
    "        while head:\n",
    "            tmp = head.next\n",
    "            head.next = None\n",
    "            nodelist.append(head)\n",
    "            head = tmp\n",
    "        \n",
    "        def sort(nodelist):\n",
    "            if len(nodelist)<=1: return nodelist\n",
    "\n",
    "            ref = random.choice(nodelist)\n",
    "            left = [node for node in nodelist if node.val<ref.val]\n",
    "            mid = [node for node in nodelist if node.val==ref.val]\n",
    "            right = [node for node in nodelist if node.val>ref.val]\n",
    "            return sort(left) + mid + sort(right)\n",
    "        \n",
    "        prenode = cur = ListNode(-1, None)\n",
    "        for node in sort(nodelist):\n",
    "            cur.next = node\n",
    "            cur = cur.next\n",
    "        return prenode.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        tmp = head\n",
    "        ans = []\n",
    "        def comp(x, y):\n",
    "            if x[0] <= y[0]:\n",
    "                return 1\n",
    "            elif x[0] > y[0]:\n",
    "                return -1\n",
    "        while(tmp):\n",
    "            ans.append((tmp.val, tmp))\n",
    "            tmp = tmp.next\n",
    "        # return head\n",
    "        ans.sort(key=lambda x:x[0])\n",
    "        # return ans\n",
    "        if len(ans) == 0:\n",
    "            return head\n",
    "        ret = ans[0][1]\n",
    "        tmp_ans = ret\n",
    "        for i in range(1, len(ans)):\n",
    "            tmp = ans[i]\n",
    "            tmp_ans.next = tmp[1]\n",
    "            tmp_ans = tmp_ans.next\n",
    "        tmp_ans.next = None\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        nodes = []\n",
    "        if head == None:\n",
    "            return head\n",
    "        while True:\n",
    "            nextNode = head.next\n",
    "            head.next = None\n",
    "            nodes.append((head,head.val))\n",
    "            head = nextNode\n",
    "            if nextNode == None:\n",
    "                break\n",
    "        nodes.sort(key=lambda x:x[1])\n",
    "\n",
    "        head = nodes[0][0]\n",
    "        for i,j in zip(nodes,nodes[1:]):\n",
    "            i[0].next = j[0]\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        node_list = list()\n",
    "        while head:\n",
    "            tmp = head.next\n",
    "            head.next = None\n",
    "            node_list.append(head)\n",
    "            head = tmp\n",
    "        \n",
    "        def sort(arr):\n",
    "            if len(arr)<=1:\n",
    "                return arr\n",
    "            ref_node = random.choice(arr)\n",
    "            left = sort([x for x in arr if x.val<ref_node.val])\n",
    "            mid = [x for x in arr if  x.val==ref_node.val]\n",
    "            right = sort([x for x in arr if x.val>ref_node.val])\n",
    "            return left + mid + right\n",
    "        \n",
    "        node_list = sort(node_list)\n",
    "        pre_node = head = ListNode(-1, None)\n",
    "        for node in node_list:\n",
    "            head.next = node\n",
    "            head = head.next\n",
    "        \n",
    "        return pre_node.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        a_list = list()\n",
    "\n",
    "        while head:\n",
    "            temp = head.next\n",
    "            head.next = None\n",
    "            a_list.append([head.val, head])\n",
    "            head = temp\n",
    "\n",
    "        first_node = ListNode(-1)\n",
    "        cur = first_node\n",
    "        a_list.sort(key=lambda x: x[0])\n",
    "\n",
    "        for a in a_list:\n",
    "            cur.next = a[1]\n",
    "            cur = cur.next\n",
    "\n",
    "        return first_node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        s = list()\n",
    "        while head:\n",
    "            s.append([head.val, head])\n",
    "            head = head.next\n",
    "        s.sort(key=lambda x: x[0])\n",
    "        for i in range(len(s)-1):\n",
    "            s[i][1].next = s[i+1][1]\n",
    "        s[-1][1].next = None\n",
    "        return s[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:    return head\n",
    "        \n",
    "        buf = []\n",
    "        point = head\n",
    "        while point:\n",
    "            buf.append([point.val, point])\n",
    "            point = point.next\n",
    "        \n",
    "        buf.sort(key=lambda x: x[0])\n",
    "        buf[-1][1].next = None\n",
    "        for idx in range(len(buf)-1):\n",
    "            buf[idx][1].next = buf[idx+1][1]\n",
    "        return buf[0][1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if head is None: return None\n",
    "        temp = []\n",
    "        while head:\n",
    "            temp.append((head, head.val))\n",
    "            head = head.next\n",
    "        temp.sort(key= lambda x : x[1])\n",
    "\n",
    "        # 重排数组\n",
    "        for i in range(len(temp)):\n",
    "            temp[i][0].next = temp[i+1][0] if i < len(temp)-1 else None\n",
    "        return temp[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        def mergeSort(l1, l2):\n",
    "            if not l1 and not l2:\n",
    "                return \n",
    "            if not l1:\n",
    "                return l2 \n",
    "            if not l2:\n",
    "                return l1 \n",
    "            p1, p2 = l1, l2\n",
    "            dummy = ListNode()\n",
    "            p = dummy\n",
    "            while p1 and p2:\n",
    "                if p1.val < p2.val:\n",
    "                    p.next = ListNode(p1.val)\n",
    "                    p1 = p1.next\n",
    "                else:\n",
    "                    p.next = ListNode(p2.val)\n",
    "                    p2 = p2.next\n",
    "                p = p.next\n",
    "            if p1:\n",
    "                p.next = p1 \n",
    "            if p2:\n",
    "                p.next = p2 \n",
    "            return dummy.next \n",
    "\n",
    "        def splitList(start, end):\n",
    "            if start == end or start.next == end:\n",
    "                start.next = None \n",
    "                return start \n",
    "            p1, p2 = start, start \n",
    "            while p2 != end:\n",
    "                p1 = p1.next \n",
    "                p2 = p2.next \n",
    "                if p2 != end:\n",
    "                    p2 = p2.next \n",
    "            l1 = splitList(start, p1)\n",
    "            l2 = splitList(p1, end)\n",
    "            return mergeSort(l1, l2)\n",
    "\n",
    "        return splitList(head, None)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def merge(l1, l2):\n",
    "    hair = ans = ListNode()\n",
    "    while l1 and l2:\n",
    "        if l1.val > l2.val:\n",
    "            ans.next = ans = ListNode(l2.val)\n",
    "            l2 = l2.next\n",
    "        else:\n",
    "            ans.next = ans = ListNode(l1.val)\n",
    "            l1 = l1.next\n",
    "    ans.next = l1 if l1 else l2\n",
    "    return hair.next\n",
    "\n",
    "def split(l):\n",
    "    slow = fast = ListNode(0, l)\n",
    "    while fast and fast.next:\n",
    "        slow = slow.next\n",
    "        fast = fast.next.next\n",
    "    tmp, slow.next = slow.next, None\n",
    "    return l, tmp\n",
    "\n",
    "def mergeSort(l):\n",
    "    if not l or not l.next: return l\n",
    "    l1, l2 = split(l)\n",
    "    return merge(mergeSort(l1), mergeSort(l2))\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        return mergeSort(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:\n",
    "            if not head:\n",
    "                return head\n",
    "            if head.next == tail:\n",
    "                head.next = None\n",
    "                return head\n",
    "            slow = fast = head\n",
    "            while fast != tail:\n",
    "                fast = fast.next\n",
    "                slow = slow.next\n",
    "                if (fast != tail):\n",
    "                    fast = fast.next\n",
    "            mid = slow\n",
    "            return merge(sortFunc(head, mid), sortFunc(mid, tail))\n",
    "            \n",
    "        def merge(head1: ListNode, head2: ListNode) -> ListNode:\n",
    "            dummyHead = ListNode(0)\n",
    "            tmp = dummyHead\n",
    "            while( head1 and head2):\n",
    "                if (head1.val < head2.val):\n",
    "                    tmp.next = ListNode(head1.val)\n",
    "                    head1 = head1.next\n",
    "                else:\n",
    "                    tmp.next = ListNode(head2.val)\n",
    "                    head2 = head2.next\n",
    "                tmp = tmp.next\n",
    "            if (head1):\n",
    "                tmp.next = head1\n",
    "            \n",
    "            if (head2):\n",
    "                tmp.next = head2\n",
    "            \n",
    "            return dummyHead.next\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        return sortFunc(head, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        dic = []\n",
    "        m = head\n",
    "        while m:\n",
    "            dic.append([m.val, m])\n",
    "            m = m.next\n",
    "        dics = sorted(dic, key= lambda x:x[0])\n",
    "        zero = ListNode(0)\n",
    "        zero.next = dics[0][1]\n",
    "        now = zero.next\n",
    "        for i in range(1, len(dics)):\n",
    "            print(dics[i][0])\n",
    "            now.next = dics[i][1]\n",
    "            now = now.next\n",
    "        now.next= None\n",
    "#         print(zero.next.next)\n",
    "        return zero.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if head==None:\n",
    "            return None\n",
    "\n",
    "        q=[]\n",
    "        i=0\n",
    "        p=head\n",
    "        while p:\n",
    "            heappush(q,(p.val,i,p))\n",
    "            p=p.next\n",
    "            i+=1\n",
    "\n",
    "        head=None\n",
    "        while q:\n",
    "            if head:\n",
    "                p.next=heappop(q)[2]\n",
    "                p=p.next\n",
    "            else:\n",
    "                head=p=heappop(q)[2]\n",
    "        p.next=None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        import heapq\n",
    "        myheap = []\n",
    "        pt = head\n",
    "        cnt = 0\n",
    "        while pt is not None:\n",
    "            heapq.heappush(myheap, (pt.val, cnt, pt))\n",
    "            cnt += 1\n",
    "            pt = pt.next\n",
    "        temp = heapq.heappop(myheap)\n",
    "        root = temp[2]\n",
    "        pt = root\n",
    "        while len(myheap) > 0:\n",
    "            temp = heapq.heappop(myheap)\n",
    "            pt.next = temp[2]\n",
    "            pt = pt.next\n",
    "        pt.next = None\n",
    "        return root     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        sl = SortedList()\n",
    "        step = 0\n",
    "        while head:\n",
    "            sl.add((head.val, step, head))\n",
    "            head = head.next\n",
    "            step += 1\n",
    "        prev = None\n",
    "        for _, _, node in sl:\n",
    "            if prev:\n",
    "                prev.next = node\n",
    "            if not head:\n",
    "                head = node\n",
    "            prev = node\n",
    "        prev.next = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def merge(p1, p2):\n",
    "            if not p1 and not p2:\n",
    "                return None \n",
    "            if not p1:\n",
    "                return p2 \n",
    "            if not p2:\n",
    "                return p1  \n",
    "            dummy = ListNode(0)\n",
    "            cur = dummy\n",
    "            while p1 and p2:\n",
    "                if p1.val <= p2.val:\n",
    "                    cur.next = ListNode(p1.val)\n",
    "                    p1 = p1.next\n",
    "                else:\n",
    "                    cur.next = ListNode(p2.val)\n",
    "                    p2 = p2.next\n",
    "                cur = cur.next \n",
    "            if p1:\n",
    "                cur.next = p1 \n",
    "            if p2:\n",
    "                cur.next = p2 \n",
    "            return dummy.next\n",
    "\n",
    "        def sortFunc(head):\n",
    "            if not head or not head.next:\n",
    "                return head \n",
    "            slow, fast = head, head.next\n",
    "            while fast and fast.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            newhead = slow.next \n",
    "            slow.next = None \n",
    "            return merge(sortFunc(head), sortFunc(newhead))\n",
    "\n",
    "        if not head:\n",
    "            return None \n",
    "        return sortFunc(head)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        '''\n",
    "        双指针快排，但空间复杂度不满足常量级\n",
    "        '''\n",
    "        def quicksort(nums,start,end):\n",
    "            if start >= end:\n",
    "                return nums\n",
    "            mid = self.partition(nums, start, end)\n",
    "            quicksort(nums, mid + 1, end)\n",
    "            quicksort(nums, start, mid - 1)\n",
    "            return nums\n",
    "        if not head:\n",
    "            return None\n",
    "        vals = []\n",
    "        cur = head\n",
    "        while cur:\n",
    "            vals.append(cur.val)\n",
    "            cur = cur.next\n",
    "        vals = quicksort(vals, 0, len(vals) - 1)\n",
    "        cur = head\n",
    "        for val in vals:\n",
    "            cur.val = val\n",
    "            cur = cur.next\n",
    "        return head\n",
    "    def partition(self,nums,start,end):\n",
    "        idx = random.randint(start,end)\n",
    "        pivot = nums[idx]\n",
    "        # 要和第一个数换！！交换是指针！！！\n",
    "        nums[start], nums[idx] = nums[idx], nums[start]\n",
    "        left, right = start + 1, end\n",
    "        while left < right:\n",
    "            while left < right and nums[left] <= pivot:\n",
    "                left += 1\n",
    "            while left < right and nums[right] >= pivot:\n",
    "                right -= 1\n",
    "            if left != right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        if left == right and nums[right] >= pivot:\n",
    "            right -= 1\n",
    "        if right != start:\n",
    "            nums[right], nums[start] = nums[start], nums[right]\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        def mergeSort(l1, l2):\n",
    "            if not l1:\n",
    "                return l2 \n",
    "            if not l2:\n",
    "                return l1 \n",
    "            dummy = ListNode(-1)\n",
    "            p = dummy\n",
    "            p1, p2 = l1, l2 \n",
    "            while p1 and p2:\n",
    "                if p1.val < p2.val:\n",
    "                    p.next = ListNode(p1.val)\n",
    "                    p1 = p1.next\n",
    "                else:\n",
    "                    p.next = ListNode(p2.val)\n",
    "                    p2 = p2.next\n",
    "                p = p.next \n",
    "            if p1:\n",
    "                p.next = p1\n",
    "            if p2:\n",
    "                p.next = p2 \n",
    "            return dummy.next\n",
    "        \n",
    "        def splitMerge(start, end):\n",
    "            if start == end:\n",
    "                return \n",
    "            if start.next == end:\n",
    "                start.next = None \n",
    "                return start\n",
    "            p1, p2 = start, start \n",
    "            #pre = None\n",
    "            while p2 != end and p2.next != end:\n",
    "                p1 = p1.next \n",
    "                p2 = p2.next \n",
    "                if p2 and p2 != end:\n",
    "                    p2 = p2.next\n",
    "            #print(p1)\n",
    "            l1 = splitMerge(start, p1)\n",
    "            #print(l1)\n",
    "            l2 = splitMerge(p1, end)\n",
    "            return mergeSort(l1, l2)\n",
    "        \n",
    "        return splitMerge(head, None)\n",
    "\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:return head\n",
    "        nodeList, node = [], head\n",
    "        while node:\n",
    "            nodeList.append((node.val, node))\n",
    "            node = node.next\n",
    "        nodeList.sort(key = lambda x:x[0])\n",
    "        for i in range(len(nodeList) - 1):nodeList[i][1].next = nodeList[i+1][1]\n",
    "        nodeList[-1][1].next = None\n",
    "        return nodeList[0][1]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        nodes = []\n",
    "        pos = head\n",
    "        while pos:\n",
    "            nodes.append((pos.val, pos))\n",
    "            pos = pos.next\n",
    "\n",
    "        nodes.sort(key=lambda x: x[0])\n",
    "        new_head = nodes[0][1]\n",
    "        pos = new_head\n",
    "        for i in range(1, len(nodes)):\n",
    "            pos.next = nodes[i][1]\n",
    "            pos = pos.next\n",
    "            pos.next = None\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        val_nodes = []\n",
    "\n",
    "        while head:\n",
    "            val_nodes.append((head.val, head))\n",
    "            head = head.next\n",
    "        \n",
    "\n",
    "        head, cur = None, None\n",
    "        for val_node in sorted(val_nodes, key=lambda x: x[0]):\n",
    "            node = val_node[1]\n",
    "            node.next = None\n",
    "\n",
    "            if not head:\n",
    "                head = node\n",
    "                cur = node\n",
    "            else:\n",
    "                cur.next = node\n",
    "                cur = node\n",
    "\n",
    "        return head  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        \n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        \n",
    "        fast = slow\n",
    "        slow = slow.next\n",
    "        fast.next = None\n",
    "        l1 = self.sortList(head)\n",
    "        l2 = self.sortList(slow)\n",
    "        return self.mergeTwoLists(l1, l2)\n",
    "    \n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        if l1 == None:\n",
    "            return l2\n",
    "        if l2 == None:\n",
    "            return l1\n",
    "        dummyNode = ListNode(-1)\n",
    "        pNode = dummyNode\n",
    "        while l1 and l2:\n",
    "            if l1.val > l2.val:\n",
    "                pNode.next = ListNode(l2.val)\n",
    "                pNode = pNode.next\n",
    "                l2 = l2.next\n",
    "            \n",
    "            else:\n",
    "                pNode.next = ListNode(l1.val)\n",
    "                pNode = pNode.next\n",
    "                l1 = l1.next\n",
    "        if l1 == None:\n",
    "            pNode.next = l2\n",
    "        if l2 == None:\n",
    "            pNode.next = l1\n",
    "        return dummyNode.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        vec = []\n",
    "        if not head:\n",
    "            return\n",
    "        \n",
    "        current = head\n",
    "        while current:\n",
    "            vec.append([current, current.val])\n",
    "            current = current.next\n",
    "        \n",
    "        vec.sort(key=lambda x:x[1])\n",
    "        for i in range(len(vec) - 1):\n",
    "            vec[i][0].next = vec[i+1][0]\n",
    "        \n",
    "        vec[-1][0].next = None\n",
    "        return vec[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        hq = []\n",
    "        cur = head\n",
    "        counter = itertools.count()\n",
    "        while cur != None:\n",
    "            next_node = cur.next\n",
    "            heapq.heappush(hq, [cur.val, next(counter), cur])\n",
    "            cur.next = None\n",
    "            cur = next_node\n",
    "\n",
    "        fake_head = ListNode()\n",
    "        cur = fake_head\n",
    "        while len(hq) != 0:\n",
    "            cur.next = heapq.heappop(hq)[2]\n",
    "            cur = cur.next\n",
    "        return fake_head.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return \n",
    "        d={}\n",
    "        node=head\n",
    "        while node:\n",
    "            if not node.val in d:\n",
    "                d[node.val]=[node]\n",
    "            else:\n",
    "                d[node.val].append(node)\n",
    "            node=node.next\n",
    "        a=sorted(d.keys())\n",
    "        imag=ListNode\n",
    "        prev=imag\n",
    "        for num in a:\n",
    "            for node in d[num]:\n",
    "                prev.next=node \n",
    "                prev=node \n",
    "        node.next=None\n",
    "        return imag.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        # group = []\n",
    "        # head_2 = head\n",
    "        # while head_2:\n",
    "        #     group.append(head_2.val)\n",
    "        #     head_2 = head_2.next\n",
    "        # group.sort()\n",
    "        # new_head = tail = ListNode(-1)\n",
    "        # for item in group:\n",
    "        #     tail.next = ListNode(item)\n",
    "        #     tail = tail.next\n",
    "        # return new_head.next\n",
    "\n",
    "        # if head is None:\n",
    "        #     return head\n",
    "        # new_head = ListNode(0)\n",
    "        # new_head.next = head\n",
    "        # sorted_head = new_head\n",
    "        # while sorted_head.next:\n",
    "        #     current = sorted_head.next\n",
    "        #     if not current.next:\n",
    "        #         break\n",
    "        #     if current.next.val < current.val:\n",
    "        #         temp = current.next\n",
    "        #         current.next = temp.next\n",
    "        #         temp.next = sorted_head.next\n",
    "        #         sorted_head.next = temp\n",
    "        #         sorted_head = new_head\n",
    "        #     else:\n",
    "        #         sorted_head = sorted_head.next\n",
    "        # sorted_head = new_head.next\n",
    "        # sorted_head = new_head\n",
    "        # sorted_list = sorted_head\n",
    "        # sorted_head = sorted_head.next\n",
    "        # return sorted_head\n",
    "\n",
    "\n",
    "        # def change(pos):\n",
    "        #     new_head = pos\n",
    "        #     if pos is None:\n",
    "        #         return head\n",
    "        #     else:\n",
    "        #         current_code = ListNode(1000000)\n",
    "        #         current_code.next = pos\n",
    "        #         while new_head.next and new_head.val < new_head.next.val:\n",
    "        #             new_head = new_head.next\n",
    "        #             current_code = current_code.next\n",
    "        #         if new_head.next is None:\n",
    "        #             return pos\n",
    "        #         if current_code.val == 1000000:\n",
    "        #             next_code = new_head.next\n",
    "        #             current_code.next = next_code\n",
    "        #             new_head.next = next_code.next\n",
    "        #             next_code.next = new_head\n",
    "        #             pos = next_code\n",
    "        #         else:\n",
    "        #             next_code = new_head.next\n",
    "        #             current_code.next = next_code\n",
    "        #             new_head.next = next_code.next\n",
    "        #             next_code.next = new_head\n",
    "        #         return change(pos)\n",
    "\n",
    "        # new_head = head\n",
    "        # return change(head)\n",
    "\n",
    "        from collections import deque\n",
    "\n",
    "\n",
    "        def merge(head_1, head_2):\n",
    "            dummy_head = cur_node = ListNode(-1)\n",
    "            while head_1 and head_2:\n",
    "                if head_1.val < head_2.val:\n",
    "                    cur_node.next = head_1\n",
    "                    head_1 = head_1.next\n",
    "                else:\n",
    "                    cur_node.next = head_2\n",
    "                    head_2 = head_2.next\n",
    "                cur_node = cur_node.next\n",
    "            if head_1 is None:\n",
    "                cur_node.next = head_2\n",
    "            else:\n",
    "                cur_node.next = head_1\n",
    "            return dummy_head.next\n",
    "\n",
    "\n",
    "        new_head = head\n",
    "        group = deque()\n",
    "        while new_head:\n",
    "            next_code = new_head.next\n",
    "            new_head.next = None\n",
    "            group.append(new_head)\n",
    "            new_head = next_code\n",
    "        print(group)\n",
    "\n",
    "        length = len(group)\n",
    "        if length == 1 or length == 0:\n",
    "            return head\n",
    "        \n",
    "        while len(group) > 1:\n",
    "            head_1 = group.popleft()\n",
    "            head_2 = group.popleft()            \n",
    "            group.append(merge(head_1,head_2))\n",
    "        return group[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:return None\n",
    "        heap = []\n",
    "        p = head \n",
    "        count = 1\n",
    "        while p:\n",
    "            heapq.heappush(heap,[p.val,count,p])\n",
    "            count += 1\n",
    "            p = p.next\n",
    "        head = heap[0][2]\n",
    "        p = head\n",
    "        while heap:\n",
    "            temp = heapq.heappop(heap)[2]\n",
    "            p.next = temp\n",
    "            p = p.next\n",
    "        p.next = None\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def merge(h):\n",
    "            if not h or not h.next: return h\n",
    "            p, q = h, h\n",
    "            while q and q.next and q.next.next:\n",
    "                p = p.next\n",
    "                q = q.next.next\n",
    "            temp = p.next\n",
    "            p.next = None\n",
    "            left = merge(h)\n",
    "            right = merge(temp)\n",
    "            return merge_sort(left, right)\n",
    "\n",
    "        def merge_sort(left, right):\n",
    "            cur = ret = ListNode()\n",
    "            while left or right:\n",
    "                if left and right:\n",
    "                    if left.val < right.val:\n",
    "                        cur.next = ListNode(left.val)\n",
    "                        left = left.next\n",
    "                    else:\n",
    "                        cur.next = ListNode(right.val)\n",
    "                        right = right.next\n",
    "                elif left:\n",
    "                    cur.next = ListNode(left.val)\n",
    "                    left = left.next\n",
    "                else:\n",
    "                    cur.next = ListNode(right.val)\n",
    "                    right = right.next\n",
    "                cur = cur.next\n",
    "            return ret.next\n",
    "\n",
    "        return merge(head) if head else head\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        cur = head\n",
    "        list1 = []\n",
    "        while cur:\n",
    "            list1.append(cur.val)\n",
    "            cur = cur.next\n",
    "        list1.sort()\n",
    "        dum = pre = ListNode(None)\n",
    "        for i in range(len(list1)):\n",
    "            pre.next = ListNode(list1[i])\n",
    "            pre = pre.next\n",
    "        return dum.next \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        cur = head\n",
    "        n = 0\n",
    "        lis = []\n",
    "        while cur:\n",
    "            n+=1\n",
    "            lis.append(cur.val)\n",
    "            cur = cur.next\n",
    "        lis.sort()\n",
    "        if lis == []:\n",
    "            return None\n",
    "        first = ListNode(lis[0])\n",
    "        cur = first\n",
    "        for i in range(1, n):\n",
    "            p = ListNode(lis[i])\n",
    "            cur.next = p\n",
    "            cur = p\n",
    "        return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        n = []\n",
    "        while head:\n",
    "            n.append(head.val)\n",
    "            head = head.next\n",
    "        n.sort()\n",
    "        h = ListNode(n[0])\n",
    "        p = h\n",
    "        for i in range(1,len(n)):\n",
    "            p.next = ListNode(n[i])\n",
    "            p = p.next\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# python3 \n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:return None\n",
    "        phead = head\n",
    "        alist = []\n",
    "        while phead:\n",
    "            alist.append(phead)\n",
    "            phead = phead.next\n",
    "        alist.sort(key=lambda x:x.val)\n",
    "        root = alist[0]\n",
    "        root.next = None\n",
    "        cur = root\n",
    "        for i in range(1,len(alist)):\n",
    "            alist[i].next = None\n",
    "            cur.next = alist[i]\n",
    "            cur = alist[i]\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "# python3\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:return None\n",
    "        alist = []\n",
    "        while head:\n",
    "            alist.append(head.val)\n",
    "            head = head.next\n",
    "        alist.sort()\n",
    "        phead = ListNode(alist[0])\n",
    "        cur = phead\n",
    "        for i in range(1,len(alist)):\n",
    "            node = ListNode(alist[i])\n",
    "            cur.next = node\n",
    "            cur = node\n",
    "        return phead\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if(not head):\n",
    "            return None\n",
    "        temp = []\n",
    "        cur = head\n",
    "        while(cur):\n",
    "            temp.append(cur.val)\n",
    "            cur = cur.next\n",
    "        temp.sort()\n",
    "        new = ListNode(temp[0])\n",
    "        cur = new\n",
    "        for i in range(1,len(temp)):    \n",
    "            cur.next = ListNode(temp[i])\n",
    "            cur = cur.next\n",
    "        return new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        result=[]\n",
    "        while head:\n",
    "            result.append(head.val)\n",
    "            head=head.next\n",
    "        result.sort()\n",
    "        head=ListNode()\n",
    "        p=head\n",
    "        for i in range(len(result)):\n",
    "            p.next=ListNode(result[i])\n",
    "            p=p.next\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        arr = []\n",
    "        cur = head\n",
    "        while cur:\n",
    "            arr.append(cur.val)\n",
    "\n",
    "            cur = cur.next\n",
    "\n",
    "        sl = sorted(arr)\n",
    "        n = len(sl)\n",
    "\n",
    "        virtual_head = ListNode(-1)\n",
    "        cur = virtual_head\n",
    "        for i in range(n):\n",
    "            cur.next = ListNode(sl[i])\n",
    "\n",
    "            cur = cur.next\n",
    "\n",
    "        return virtual_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        node_list = []\n",
    "        data_list = []\n",
    "        pos = 0\n",
    "        while head:\n",
    "            node_list.append(head)\n",
    "            data_list.append((pos, head.val))\n",
    "            head = head.next\n",
    "            pos += 1\n",
    "        data_list = sorted(data_list, key = lambda x:x[1])\n",
    "        data_list = [x[0] for x in data_list]\n",
    "\n",
    "        head = None\n",
    "        tmp_node = None\n",
    "        for pos in data_list:\n",
    "            if head is None:\n",
    "                head = node_list[pos]\n",
    "                tmp_node = head\n",
    "            else:\n",
    "                tmp_node.next = node_list[pos]\n",
    "                tmp_node = tmp_node.next\n",
    "        if tmp_node is not None:\n",
    "            tmp_node.next = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def paixu(h):\n",
    "            if not h or not h.next:\n",
    "                return h\n",
    "            p, q = h, h\n",
    "            while q and q.next and q.next.next:\n",
    "                p = p.next\n",
    "                q = q.next.next\n",
    "            temp = p.next\n",
    "            p.next = None\n",
    "            left = paixu(h)\n",
    "            right = paixu(temp)\n",
    "            return hebing(left, right)\n",
    "\n",
    "        def hebing(left, right):\n",
    "            cur = res = ListNode()\n",
    "            while left or right:\n",
    "                if left and right:\n",
    "                    if left.val < right.val:\n",
    "                        cur.next = ListNode(left.val)\n",
    "                        left = left.next\n",
    "                    else:\n",
    "                        cur.next = ListNode(right.val)\n",
    "                        right = right.next\n",
    "                elif left:\n",
    "                    cur.next = ListNode(left.val)\n",
    "                    left = left.next\n",
    "                else:\n",
    "                    cur.next = ListNode(right.val) \n",
    "                    right = right.next\n",
    "                cur = cur.next               \n",
    "               \n",
    "            return res.next\n",
    "\n",
    "        return paixu(head)                             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        cur = head\n",
    "        stack = []\n",
    "        while cur:\n",
    "            stack.append(cur.val)\n",
    "            cur = cur.next\n",
    "        stack.sort()\n",
    "        cur = dummy\n",
    "        while stack:\n",
    "            cur.next = ListNode(stack.pop(0))\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# class Solution:\n",
    "#     def sortList(self, head: ListNode | None) -> ListNode | None:\n",
    "#         def sort(head: ListNode | None, tail: ListNode | None = None):\n",
    "#             if head == tail or head.next == tail:\n",
    "#                 return head\n",
    "#             mid = partition(head, tail)\n",
    "#             sort(head, mid)\n",
    "#             sort(mid.next, tail)\n",
    "#\n",
    "#         def partition(head: ListNode, tail: ListNode | None) -> ListNode:\n",
    "#             i, j = head, head.next\n",
    "#             while j != tail:\n",
    "#                 if j.val < head.val:\n",
    "#                     i = i.next\n",
    "#                     i.val, j.val = j.val, i.val\n",
    "#                 j = j.next\n",
    "#             head.val, i.val = i.val, head.val\n",
    "#             return i\n",
    "#\n",
    "#         sort(head)\n",
    "#         return head\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode | None) -> ListNode | None:\n",
    "        ans = []\n",
    "        while head:\n",
    "            ans.append(head.val)\n",
    "            head = head.next\n",
    "        ans.sort(reverse=True)\n",
    "        head = None\n",
    "        for n in ans:\n",
    "            head = ListNode(n, head)\n",
    "        return head\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # if not head:\n",
    "        #     return head\n",
    "\n",
    "        # # 将链表的值存入一个数组\n",
    "        # values = []\n",
    "        # curr = head\n",
    "        # while curr:\n",
    "        #     values.append(curr.val)\n",
    "        #     curr = curr.next\n",
    "\n",
    "        # # 对数组进行升序排序\n",
    "        # values.sort()\n",
    "\n",
    "        # # 使用虚拟头节点\n",
    "        # dummy_head = ListNode()\n",
    "        # curr = dummy_head\n",
    "\n",
    "        # # 遍历排序后的数组并重新构建链表\n",
    "        # for value in values:\n",
    "        #     curr.next = ListNode(value)\n",
    "        #     curr = curr.next\n",
    "\n",
    "        # return dummy_head.next\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        values = []\n",
    "        curr = head\n",
    "        while curr:\n",
    "            values.append(curr.val)\n",
    "            curr = curr.next\n",
    "        \n",
    "        values.sort()\n",
    "\n",
    "        dummy_head = ListNode()\n",
    "        curr = dummy_head\n",
    "\n",
    "        for value in values:\n",
    "            curr.next = ListNode(value)\n",
    "            curr = curr.next\n",
    "        return dummy_head.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        cur = head\n",
    "        ls = []\n",
    "        while cur:\n",
    "            ls.append(cur.val)\n",
    "            cur = cur.next\n",
    "        ls.sort()\n",
    "        dummy = ListNode()\n",
    "        cur = dummy\n",
    "        for num in ls:\n",
    "            node = ListNode(num)\n",
    "            cur.next = node\n",
    "            cur = cur.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        result = []\n",
    "        if not head:\n",
    "            return None\n",
    "        while head:\n",
    "            result.append(head.val)\n",
    "            head = head.next\n",
    "        result.sort()\n",
    "        hair = ListNode(0)\n",
    "        cur = hair\n",
    "        for i in range(len(result)):\n",
    "            cur.next = ListNode(result[i])\n",
    "            cur = cur.next\n",
    "        return hair.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if not head: return None\n",
    "        stack  = []\n",
    "        start = head\n",
    "        while start:\n",
    "            stack.append(start.val)\n",
    "            start = start.next\n",
    "        sored_stack = sorted(stack)\n",
    "        dummy = ListNode(0)\n",
    "        start = dummy\n",
    "        for each in sored_stack:\n",
    "            start.next = ListNode(each)\n",
    "            start = start.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def middleList(head: Optional[ListNode]):\n",
    "            if not head or not head.next : return head\n",
    "            slow,fast = head,head\n",
    "            while fast and fast.next and fast.next.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            temp = slow.next\n",
    "            slow.next = None\n",
    "            left = middleList(head)\n",
    "            right = middleList(temp)\n",
    "\n",
    "            return merge_sort(left,right)\n",
    "\n",
    "        \n",
    "        def merge_sort(left,right):\n",
    "            cur = ret = ListNode()\n",
    "            while left or right:\n",
    "                if left and right:\n",
    "                    if left.val < right.val:\n",
    "                        cur.next = ListNode(left.val)\n",
    "                        left = left.next\n",
    "\n",
    "                    else:\n",
    "                        cur.next = ListNode(right.val)\n",
    "                        right = right.next\n",
    "                elif left:\n",
    "                    cur.next = ListNode(left.val)\n",
    "                    left = left.next\n",
    "                else:\n",
    "                    cur.next = ListNode(right.val)\n",
    "                    right = right.next\n",
    "                cur = cur.next\n",
    "            return ret.next\n",
    "        return middleList(head) if head else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        data = collections.defaultdict(list)\n",
    "        tmp = head\n",
    "\n",
    "        while tmp is not None:\n",
    "            data[ tmp.val ].append(tmp)\n",
    "            tmp = tmp.next\n",
    "        \n",
    "        dummy = ListNode()\n",
    "        tmp = dummy\n",
    "        for key in sorted(data.keys()):\n",
    "            for item in data[key]:\n",
    "                tmp.next = item\n",
    "                tmp = tmp.next\n",
    "        \n",
    "        tmp.next = None\n",
    "        return dummy.next\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        def merge(h):\n",
    "            if not h or not h.next:\n",
    "                return h\n",
    "            p,q = h,h\n",
    "            while q and q.next and q.next.next:\n",
    "                p = p.next\n",
    "                q = q.next.next\n",
    "            temp = p.next\n",
    "            p.next = None\n",
    "            left = merge(h)\n",
    "            right = merge(temp)\n",
    "            return merge_sort(left,right)\n",
    "        \n",
    "        def merge_sort(left,right):\n",
    "            dummy = cur = ListNode(0)\n",
    "            while left or right:\n",
    "                if left and right:\n",
    "                    if left.val<right.val:\n",
    "                        cur.next = ListNode(left.val)\n",
    "                        left = left.next\n",
    "                    else:\n",
    "                        cur.next = ListNode(right.val)\n",
    "                        right = right.next\n",
    "                elif left:\n",
    "                    cur.next = ListNode(left.val)\n",
    "                    left = left.next\n",
    "                else:\n",
    "                    cur.next = ListNode(right.val)\n",
    "                    right = right.next\n",
    "                cur = cur.next\n",
    "            return dummy.next\n",
    "        return merge(head) if head else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def merge(self,head1,head2):\n",
    "        p = head1\n",
    "        q = head2\n",
    "        dummy = ListNode\n",
    "        r = dummy\n",
    "        while p!=None and q!=None:\n",
    "            if p.val<q.val:\n",
    "                r.next = ListNode(p.val)\n",
    "                r=r.next\n",
    "                p=p.next\n",
    "            else:\n",
    "                r.next = ListNode(q.val)\n",
    "                r=r.next\n",
    "                q=q.next\n",
    "        while p!=None:\n",
    "            r.next = ListNode(p.val)\n",
    "            r=r.next\n",
    "            p=p.next\n",
    "        while q!=None:\n",
    "            r.next = ListNode(q.val)\n",
    "            r=r.next\n",
    "            q=q.next\n",
    "        return dummy.next\n",
    "        \n",
    "\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        if head==None or head.next==None:\n",
    "            return head\n",
    "        dummy = ListNode(0,head)\n",
    "        slow = dummy\n",
    "        fast = dummy\n",
    "        while fast!=None and fast.next!=None:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "            if fast!=None:\n",
    "                fast = fast.next\n",
    "        head1 = head\n",
    "        head2 = slow.next\n",
    "        slow.next = None\n",
    "        head1 = self.sortList(head1)\n",
    "        head2 = self.sortList(head2)\n",
    "        return self.merge(head1,head2)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        cur = head\n",
    "        res = []\n",
    "        while cur:\n",
    "            res.append(cur.val)\n",
    "            cur = cur.next\n",
    "        res.sort(reverse = False)\n",
    "        ans = None\n",
    "        while res:\n",
    "            node = ListNode(res.pop())\n",
    "            node.next = ans\n",
    "            ans = node\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        phead = head\n",
    "\n",
    "        l = []\n",
    "        while phead:\n",
    "            l.append(phead.val)\n",
    "            phead = phead.next\n",
    "        \n",
    "        l.sort()\n",
    "\n",
    "        rhead = ListNode(0)\n",
    "        thead = rhead\n",
    "        for i in l:\n",
    "            t = ListNode(i)\n",
    "            thead.next = t\n",
    "            thead = thead.next\n",
    "        \n",
    "        return rhead.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        cur = head\n",
    "        nums = []\n",
    "        while cur:\n",
    "            nums.append(cur.val)\n",
    "            cur = cur.next\n",
    "        nums.sort()\n",
    "        cur = ans = ListNode()\n",
    "        for num in nums:\n",
    "            cur.next = ListNode(num)\n",
    "            cur = cur.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def add_node(self, val_list):\n",
    "        head = ListNode()\n",
    "        current = head\n",
    "        for val in val_list:\n",
    "            current.next = ListNode(val, current.next)\n",
    "            current = current.next\n",
    "\n",
    "        return ListNode(next=head).next.next\n",
    "\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        head = ListNode(next=head)\n",
    "        cur_node = head\n",
    "        new_list = []\n",
    "        while cur_node.next:\n",
    "            new_list.append(cur_node.next.val)\n",
    "            cur_node = cur_node.next\n",
    "        \n",
    "        new_list.sort()\n",
    "        return self.add_node(new_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        ans = ListNode(0, None)\n",
    "        t = ans\n",
    "        cur = head\n",
    "        res = []\n",
    "        while cur:\n",
    "            res.append(cur.val)\n",
    "            cur = cur.next\n",
    "        res.sort()\n",
    "        n = len(res)\n",
    "        for i in range(n):\n",
    "            tmp = ListNode(res[i], None)\n",
    "            t.next = tmp\n",
    "            t = tmp\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        nums = []\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nums.append(cur.val)\n",
    "            cur = cur.next\n",
    "        nums.sort()\n",
    "        cur = ans = ListNode()\n",
    "        for i in range(len(nums)):\n",
    "            cur.next = ListNode(nums[i])\n",
    "            cur = cur.next\n",
    "        return ans.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        node_list = []\n",
    "        if not head:\n",
    "            return head\n",
    "        while head is not None:\n",
    "            node_list.append(head.val)\n",
    "            head = head.next\n",
    "        print(node_list)\n",
    "        node_list.sort()\n",
    "        \n",
    "        res = ListNode()\n",
    "        cur = res\n",
    "        for node in node_list:\n",
    "            cur.next = ListNode(val = node)\n",
    "            cur = cur.next\n",
    "        # cur = None\n",
    "        return res.next\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
